package com.zjj.algorithm.learning.leetcode.sort;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 1508. 子数组和排序后的区间和 中等
 * 给你一个数组 nums ，它包含 n 个正整数。你需要计算所有非空连续子数组的和，并将它们按升序排序，得到一个新的包含 n * (n + 1) / 2 个数字的数组。
 * <p>
 * 请你返回在新数组中下标为 left 到 right （下标从 1 开始）的所有数字和（包括左右端点）。由于答案可能很大，请你将它对 10^9 + 7 取模后返回。
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums = [1,2,3,4], n = 4, left = 1, right = 5
 * 输出：13
 * 解释：所有的子数组和为 1, 3, 6, 10, 2, 5, 9, 3, 7, 4 。将它们升序排序后，我们得到新的数组 [1, 2, 3, 3, 4, 5, 6, 7, 9, 10] 。下标从 le = 1 到 ri = 5 的和为 1 + 2 + 3 + 3 + 4 = 13 。
 * 示例 2：
 * <p>
 * 输入：nums = [1,2,3,4], n = 4, left = 3, right = 4
 * 输出：6
 * 解释：给定数组与示例 1 一样，所以新数组为 [1, 2, 3, 3, 4, 5, 6, 7, 9, 10] 。下标从 le = 3 到 ri = 4 的和为 3 + 3 = 6 。
 * 示例 3：
 * <p>
 * 输入：nums = [1,2,3,4], n = 4, left = 1, right = 10
 * 输出：50
 *
 * @author zjj_admin
 * @date 2022/11/16 15:26
 */
public class RangeSumOfSortedSubarraySums {

    static final int MOD = (int) (1e9 + 7);

    public static void main(String[] args) {

//        int[] arr = new int[]{1, 2, 3, 4};
//        int sum = rangeSum1(arr, 4, 1, 5);
//        System.out.println("sum = " + sum);


        int[] arr = new int[]{20, -2, 0, 5, 12, 32, 15, 42, 36};
        aesQuickSort(arr, 0, arr.length - 1);
        System.out.println("arr = " + Arrays.toString(arr));

    }


    /**
     * 时间
     * 734 ms
     * 击败
     * 5.26%
     * 内存
     * 41.3 MB
     * 击败
     * 81.42%
     *
     * @param nums
     * @param n
     * @param left
     * @param right
     * @return
     */
    public static int rangeSum(int[] nums, int n, int left, int right) {
        int len = (nums.length * (nums.length + 1)) / 2;
        int[] newArr = new int[len];
        int index = 0;
        int num;
        for (int i = 0; i < nums.length; i++) {
            num = 0;
            for (int j = i; j < nums.length; j++) {
                num += nums[j];
                newArr[index++] = num;
            }
        }
        aesQuickSort(newArr, 0, newArr.length - 1);
        long sum = 0;
        for (int i = left - 1; i < right; i++) {
            sum += newArr[i];
        }
        long number = (10 * 10 * 10 * 10 * 10 * 10 * 10 * 10 * 10 + 7);
        return (int) (sum % number);
    }


    /**
     * 对数组进行排序，使用快速排序
     *
     * @param heights
     * @param left
     * @param right
     */
    public static void aesQuickSort(int[] heights, int left, int right) {
        if (left >= right) {
            return;
        }
        int l = left;
        int r = right;
        //以最右边的数据为 pivot
        int pivot = heights[right];
        while (l < r) {
            //从左向右依次遍历，只要找到了比 pivot 大的数据就与 pivot 交换
            while (l < r && heights[l] < pivot) {
                l++;
            }
            //说明在 pivot 之前找到了一个比 pivot 大的值
            if (l < r) {
                //此时的 pivot 为 heights[l]
                heights[r] = heights[l];
                r--;
            }
            //从右向左依次遍历，当找到一个比 pivot 小的数据就和 pivot 交换
            while (l < r && heights[r] > pivot) {
                r--;
            }

            //当找到了一个数据在比 pivot 小的时候，就交换
            if (l < r) {
                heights[l] = heights[r];
                l++;
            }
        }
        heights[r] = pivot;

        aesQuickSort(heights, left, l - 1);
        aesQuickSort(heights, l + 1, right);

    }


    /**
     * 时间
     * 70 ms
     * 击败
     * 51.70%
     * 内存
     * 46.8 MB
     * 击败
     * 49.54%
     *
     * @param nums
     * @param n
     * @param left
     * @param right
     * @return
     */
    public static int rangeSum1(int[] nums, int n, int left, int right) {
        int[] valSum = new int[n * (n + 1) / 2];
        int index = 0;

        for (int i = 0; i < n; i++) {
            int sum = 0;
            for (int j = i; j < n; j++) {
                sum += nums[j];
                valSum[index++] = sum;
            }
        }
        Arrays.sort(valSum);
        int res = 0;

        for (int i = left - 1; i < right; i++) {
            res = (res + valSum[i]) % MOD;
        }
        return res;
    }
}
